package tree;

import java.util.*;

public class BinaryTree<E> {
    public TreeNode root;

     public List<E> preOrder(){
         return getPreOrder(this.root);
     }
     // 根 左 右
     private List<E> getPreOrder(TreeNode root){
         List<E> list = new ArrayList<>();
         if(root == null) return list;
         list.add((E)root.val);
         list.addAll(getPreOrder(root.left));
         list.addAll(getPreOrder(root.right));
         return list;
     }

    public List<E> inOrder(){
        return getInOrder(this.root);
    }
    // 左 根 右
    private List<E> getInOrder(TreeNode root) {
        List<E> list = new ArrayList<>();
        if(root == null) return list;
        list.addAll(getPreOrder(root.left));
        list.add((E)root.val);
        list.addAll(getPreOrder(root.right));
        return list;
    }

    public List<E> postOrder(){
        return getInOrder(this.root);
    }
    // 左 右 根
    private List<E> getPostOrder(TreeNode root) {
        List<E> list = new ArrayList<>();
        if(root == null) return list;
        list.addAll(getPreOrder(root.left));
        list.addAll(getPreOrder(root.right));
        list.add((E)root.val);
        return list;
    }

    public int size(){
         return getSize(root);
    }

    private int getSize(TreeNode root) {
         if(root == null) return 0;
         return 1 + getSize(root.left) + getSize(root.right);
    }

    public int leafSize(){
         return getLeafSize(root);
    }

    private int getLeafSize(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return getLeafSize(root.left) + getLeafSize(root.right);
    }

    public int specSize(int deep){
         return getSpecSize(root,deep);
    }

    private int getSpecSize(TreeNode root, int deep) {
        List<List<E>> list = sequenceTravel(root);
        return list.get(deep%list.size()).size();
    }

    public List<List<E>> sequenceTravel(TreeNode root){
        List<List<E>> list = new ArrayList<>();
        sequenceHelper(root,list,0);
        return list;
    }

    private void sequenceHelper(TreeNode root,List<List<E>> list,int deep){
         if(root == null) return ;
         if(deep >= list.size()){
             list.add(new ArrayList<>());
         }
         list.get(deep).add((E)root.val);
         sequenceHelper(root.left,list,deep + 1);
         sequenceHelper(root.right,list,deep+1);
    }

    public TreeNode search(E val){
         return searchHelper(root,val);
    }

    private TreeNode searchHelper(TreeNode root, E val) {
         if(root == null) return null;
         if(root.val.equals(val)) return root;
         TreeNode leftSearch = searchHelper(root.left,val);
         if(leftSearch != null) return leftSearch;
         return searchHelper(root.right,val);
    }

    public static boolean isSameTree(TreeNode p,TreeNode q){
        if(p == null && q == null) return true;
        if((p != null && q == null)||(p == null && q != null)) return false;
        if(!p.val.equals(q.val)) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    public static boolean isSubTree(TreeNode root,TreeNode subRoot){
         if(root == null && subRoot != null) return false;
         if(!root.val.equals(subRoot.val)){
             return isSubTree(root.left,subRoot) || isSubTree(root.right,subRoot);
         }
         return isSameTree(root,subRoot) || isSubTree(root.left,subRoot) || isSubTree(root.right,subRoot); // 重复元素处理
    }

    public int height(){
         return getHeight(root);
    }

    private int getHeight(TreeNode root) {
         if(root == null) return 0;
         return 1 + Math.max(getHeight(root.left),getHeight(root.right));
    }

    public boolean isBalance(){
         return balance(root);
    }

    private boolean balance(TreeNode root) {
         return balanceAndHigh(root) > 0;
    }

    // 这个思想 非常好 ！ （减少了递归次数！）
    // 如果 树平衡返回树的高度，如果树不平衡返回 -1;
    private int balanceAndHigh(TreeNode root){
         if(root == null) return 0;
         int leftHigh = balanceAndHigh(root.left);
         if(leftHigh < 0) return -1; // 左子树不平衡
         int rightHigh = balanceAndHigh(root.right);
         if(rightHigh < 0) return -1;// 右子树不平衡
         int diff = leftHigh - rightHigh; // 计算高度差
         if(diff < -1 || diff > 1) return -1; // 左右子树之间高度差绝对值大于1
         return 1 + Math.max(leftHigh,rightHigh);
    }

    public List<List<E>> leverOrder(){
         return leverOrderHelper(root);
    }

    private List<List<E>> leverOrderHelper(TreeNode root) {
          List<List<E>> list = new ArrayList<>();
          if(root == null) return list;
          Queue<Element> queue = new LinkedList<>();
          queue.offer(new Element(root,0));
          while(!queue.isEmpty()){
              Element element = queue.poll();
              int lever = element.lever;
              TreeNode node = element.node;
              if(lever >= list.size()){
                  list.add(new ArrayList<>());
              }
              list.get(lever).add((E)node.val);
              if(node.left != null){
                  queue.offer(new Element(node.left,lever +1));
              }
              if(node.right != null){
                  queue.offer(new Element(node.right,lever + 1));
              }
          }
          return list;
    }

    // 是不是一棵 完全二叉树！
    public boolean isCompleteTree(){
         return completeHelper(root);
    }

    // 判断一颗树是否是完全二叉树
    // 如果树root 是完全二叉树
    // 则层序遍历到null 后 再不会遍历到非空节点！
    private boolean completeHelper(TreeNode root) {
         Queue<TreeNode> queue = new LinkedList<>();
         queue.offer(root);
         while(true){
             TreeNode node = queue.poll();
             if(node == null) break;
             queue.offer(node.left);
             queue.offer(node.right);
         } // 如果是完全二叉树，层序遍历完成后，队列为空！
         return queue.size() == 0;
    }

    // 通过前序和中序的遍历结果构建一颗唯一的二叉树！
    // 分治思路！
    public TreeNode buildTree(E[] preorder,E[] inorder){
        if(preorder.length <= 0) return null;
        Map<E,Integer> in_index = new HashMap<>();
        for(int i = 0;i < inorder.length; i++){
            in_index.put(inorder[i],i);
        }
        return helper(preorder,inorder,0,preorder.length,0,inorder.length,in_index);
//        List<E> preList = toList(preorder);
//        List<E> inList = toList(inorder);
//        return helper(preList,inList);
    }

    private TreeNode helper( List<E> preList, List<E> inList) {
         if(preList.size() <= 0) return null;
         TreeNode root = new TreeNode(preList.get(0));
         int leftSize = inList.indexOf(root.val);
         List<E> l_preList = preList.subList(1,1+leftSize);
         List<E> l_inList = inList.subList(0,leftSize);
         root.left = helper(l_preList,l_inList);
         List<E> r_preList = preList.subList(1+leftSize,preList.size());
         List<E> r_inList = inList.subList(leftSize + 1,inList.size());
         root.right = helper(r_preList,r_inList);
         return root;
    }


    // 分别锁定中序，前序 边界！[) ;
    private TreeNode helper(E[] preorder, E[] inorder, int preLB, int preRB, int inLB, int inRB, Map<E,Integer> in_index){
        if(preLB >= preRB) return null;

        TreeNode root = new TreeNode(preorder[preLB]);

        int leftSize = in_index.get(root.val) - inLB;

        // 左子树的边界线确定！
        int l_preLB = preLB + 1;
        int l_preRB = preRB + leftSize + 1;
        int l_inLB = inLB;
        int l_inRB = inRB + leftSize;
        root.left = helper(preorder,inorder,l_preLB,l_preRB,l_inLB,l_inRB,in_index);

        // 右子树边界线确定!
        int r_preLB = preLB + leftSize + 1;
        int r_preRB = preRB;
        int r_inLB = inLB + leftSize + 1;
        int r_inRB = inRB;
        root.right = helper(preorder,inorder,r_preLB,r_preRB,r_inLB,r_inRB,in_index);

        return root;
     }

     private int cur_index = 0;
     private TreeNode helper(E[] preorder,E[] inorder,int left,int right,Map<E,Integer> in_index){
         if(left >= right || preorder.length <= 0) return null;
         TreeNode root = new TreeNode(preorder[cur_index]);
         int index = in_index.get(root.val);
         cur_index++; // 用掉一个节点!
         // 只要锁定 在中序遍历中 左子树的范围即可!
         root.left = helper(preorder,inorder,left,index,in_index);
         root.right = helper(preorder,inorder,index + 1,right,in_index);
         return root;
     }

    private List<E> toList(E[] order){
         List<E> list = new ArrayList<>();
         for(E e : order){
             list.add(e);
         }
         return list;
    }

    public void preorderAppend(StringBuilder sb,TreeNode root){
         if(root == null) return ;
         sb.append('(');
         sb.append(root.val);
         if(root.left == null){
             sb.append("()"); // 不能省略!
             preorderAppend(sb,root.right);
         }else {
             preorderAppend(sb,root.left);
             if(root.right != null){
                 preorderAppend(sb,root.right);
             }
         }
         sb.append(')');
    }

    public String toString(TreeNode root){
         if(root == null) return "";
         StringBuilder sb = new StringBuilder();
         preorderAppend(sb,root);
         sb.delete(0,1);
         sb.delete(sb.length() - 1,sb.length());
         return sb.toString();
    }

    // 二叉搜索树转换成双向链表
    public TreeNode changeToLinkedList(TreeNode root){
         inorder(root);
         return head;
    }

    private void inorder(TreeNode root){
         if(root == null) return ;
         inorder(root.left);
         link(root);
         inorder(root.right);
    }
    TreeNode head = null;
    TreeNode last = null;
    private void link(TreeNode node){
         if(last == null){
             head = last = node;
             return;
         }
         last.right = node;
         node.left = last;
         last = node;
    }

    // 根据前序遍历带空字符 == '#' 的字符串!
    public TreeNode buildTree(String preorder){
        return buildTreeBy(preorder);
    }
    int index = 0;
    private TreeNode preorder(String preorder){
        if(index >= preorder.length()) return null;
        if(preorder.charAt(index) == '#') return null;
        root = new TreeNode(preorder.charAt(index));
        index++;
        root.left = preorder(preorder);
        root.right = preorder(preorder);
        return root;
    }

    private static BuildResult buildTreeList(List<Character> preorder) {
        if (preorder.size() == 0) {
            return new BuildResult(null, 0);
        }

        // 先取出根的值
        char rootVal = preorder.get(0);    // size() > 0，肯定不越界
        if (rootVal == '#') {
            return new BuildResult(null, 1);    // 为什么 size 是 1，是因为我们实际上用了一个值(#)
        }

        // 构建我们的根结点
        TreeNode root = new TreeNode(rootVal);
        // 构建 root 的左子树
        List<Character> leftPreorder = preorder.subList(1, preorder.size());
        BuildResult left = buildTreeList(leftPreorder);
        // 我们希望在构建左子树的过程中可以返回两个信息：
        // 1. 构建好的左子树的根                          有
        // 2. 再构建左子树过程中使用了序列中的多少个元素    没有
        // 虽然 java 的语法默认不支持，但我们可以把两个信息包装成一个类，然后统一返回即可
        root.left = left.rootOfTree;

        // 构建 root 的右子树
        // 我们的代码写不下去了，因为没办法从 preorder 中切割出构建右子树需要的序列
        // 为什么切割不出来，是因为我们不知道构建左子树的过程中，用了序列中的多少个元素
        // preorder 是用来构建整棵树的序列（很可能超出构建整棵树的需要）
        // 第一个元素，是根的值；被构建根用掉了
        // 从第二个元素开始，取 leftUsedSize，是左子树的值，被构建左子树的时候用掉了
        // 那么从 1 + leftUsedSize 之后，就是构建右子树需要的序列
        List<Character> rightPreOrder = preorder.subList(1 + left.usedSize, preorder.size());
        BuildResult right = buildTreeList(rightPreOrder);
        root.right = right.rootOfTree;
        // 返回整棵树的根
        // 我们构建整棵树用掉的值的数量 = 根用掉的（1）+ 左子树用掉的（left.usedSize) + 右子树用掉的（right.usedSize)
        return new BuildResult(root, 1 + left.usedSize + right.usedSize);
    }

    private static TreeNode buildTreeBy(String preorder) {
        List<Character> preorderList = new ArrayList<>();
        for (char c : preorder.toCharArray()) {
            preorderList.add(c);
        }

        BuildResult result =  buildTreeList(preorderList);
        return result.rootOfTree;
    }

}

// 这个类是专门包装两个信息：1）构建好的二叉树的根（可能是 null）  2）构建二叉树过程中，用了序列中的多少个值
class BuildResult {
    TreeNode rootOfTree;    // 构建好的树的根
    int usedSize;           // 使用了序列中的多少个值

    BuildResult(TreeNode root, int size) {
        this.rootOfTree = root;
        this.usedSize = size;
    }
}